UVA12177 First Knight

dp(i,j)dp(i,j) 表示由 (i,j)(i,j) 走到 (n,m)(n,m) 的期望步数。

那么显然有转移:

dp(i,j)=1+(up(i,j)×dp(i+1,j)+down(i,j)×dp(i1,j)+left(i,j)×dp(i,j1)+right(i,j)×dp(i,j+1))dp(i,j)=1+(up(i,j) \times dp(i+1,j) + down(i,j) \times dp(i-1,j) + left(i,j) \times dp(i,j-1) + right(i,j) \times dp(i,j+1))

阅读全文 »

CF685B Kay and Snowflake

这道题应该算是 CSP2019 树的重心\text{CSP2019 树的重心} 的前置知识了吧。可惜之前我并没有做过。

对于一棵以 uu 为根的子树,它的重心只可能在点 uu 或 以点 uu 的重儿子为根的子树中。

那么类比 lca\text{lca} 倍增父亲,树的重心倍增重儿子。

阅读全文 »

UVA10859 Placing Lampposts

nn 个点 mm 条边的无向无环图,其实就是一个森林。

题目要求最小化两个量:灯数和只被一边照亮的边数。

一个做法是定义两个 dpdp 数组,分别表示最小灯数和在灯数最小情况下的一边被照亮的最小边数。

阅读全文 »

P6218 [USACO06NOV] Round Numbers S

首先有个想法,如果该位为 00 且不是前导 00,则将 00 的数量加一,最后看 00 是否出现了至少 len2\lceil \frac{\text{len}}{2} \rceil 次。

但这样有个问题,比如在 n=8(1000)2n=8(1000)_2 时, 2(0010)2(0010) 就不会被计入答案 ,原因是 22 的前导 00 也算在了它二进制的位数中。

所以还要记录前导零的数量 leadnum\text{leadnum},最后判断是否出现至少 lenleadnum2\lceil \frac{\text{len}-\text{leadnum}}{2} \rceil 即可。

阅读全文 »

SP17247 Digit Sum

每个数的数字和的和其实就是所有数字与它出现次数的积的和。

那么对于 090-9 ,依次像 P2602 [ZJOI2010]数字计数 统计出现次数就可以了。

具体做法也很简单,记录前 pospos 位某个数字出现次数 sumsum,记忆化搜索即可通过。

阅读全文 »

AT5200 [AGC038C] LCMs

i=1nj=i+1nlcm(Ai,Aj)\sum_{i=1}^n\sum_{j=i+1}^n\text{lcm}(A_i,A_j)

i=1nj=1nlcm(Ai,Aj)i=1nAi2\frac{\sum_{i=1}^n\sum_{j=1}^n\text{lcm}(A_i,A_j)-\sum_{i=1}^nA_i}{2}

阅读全文 »